#include <iostream>  
  
template <typename T>  //T是一个模板用来代替int,double等等，可以不用再去定义int,double了。
class ListNode {  
public:  
    T data;  
    ListNode<T>* next;  
  
    ListNode(T data) : data(data), next(nullptr) {} //初始化列表 
};  
template <typename T>
class ListNode{
    T data;
    ListNode<int>* next;
    ListNode(T data) : data(data),next(nullptr){}
};
  
template <typename T>  
class LinkedList {  
private:  
    ListNode<T>* head;  
    int size;  
    ListNode<T>* head;
    int size;
public:  
    LinkedList() : head(nullptr), size(0) {}  
  
    ~LinkedList() {  //释放空间       
        while (head != nullptr) {  
            ListNode<T>* temp = head;  
            head = head->next;  
            delete temp;  
        }  
    } 
    LinkNode() : head(nullptr), size(0){} 
    ~LinkNode(){
        while(head != nullptr){
            ListNode<T>* temp = head;
            head = head -> next;
            delete temp;
        }
    }
  
    void insert(T data) {  
        ListNode<T>* newNode = new ListNode<T>(data);  
        if (head == nullptr) {  
            head = newNode;  
        } else {  
            ListNode<T>* current = head;  
            while (current->next != nullptr) {  
                current = current->next;  
            }  
            current->next = newNode;  
        }  
        size++;  
    }  
    void insert(T data){
        ListNode<T>* newNode = new ListNode<T>(data)
        if(head == nullptr){
            head = newNode;
        }else{
            ListNode<T>* current = head;
            while(current ->next!=nullptr){
                current = current->next;
            }
            current = newNode;
        }
    }
  
    void remove(T data) {  
        if (head == nullptr) return;  
  
        if (head->data == data) {  
            ListNode<T>* temp = head;  
            head = head->next;  
            delete temp;  
            size--;  
            return;  
        }  
  
        ListNode<T>* current = head;  
        while (current->next != nullptr && current->next->data != data) {  
            current = current->next;  
        }  
  
        if (current->next != nullptr) {  
            ListNode<T>* temp = current->next;  
            current->next = current->next->next;  
            delete temp;  
            size--;  
        }  
    } 
    void remove(T data){
        if(head == nullptr) return ;
        if(head ->data == data){
            ListNode<T>*temp = head;
            head = head ->next;
            delete temp;
            size--;
            return;
        } 
        ListNode<T>* current = head;
        while(current ->next != nullptr && current ->data !=data){
            current = current->next;
        } 
        if(current ->next != nullptr){
            ListNode<T>* temp = current ->next;
            current -> next =current ->next ->next;
            delete temp;
            size--;
            return ;
        }      
    } 
  
    bool search(T data) {  
        ListNode<T>* current = head;  
        while (current != nullptr) {  
            if (current->data == data) {  
                return true;  
            }  
            current = current->next;  
        }  
        return false;  
    }  

    bool search(T data){
        ListNode<T>* current = head;
        while(current != nullptr){
            if(current ->data ==data)
            {
                renturn true;
            }
            current = current -> next;
        }
        return false;
    }
  
    void printList() {  
        ListNode<T>* current = head;  
        while (current != nullptr) {  
            std::cout << current->data << " ";  
            current = current->next;  
        }  
        std::cout << std::endl;  
    }  
  
    int getSize() {  
        return size;  
    }  
    //
    void printfList(){
        ListNode<T>* current = head;
        while(current != nullptr){
            std::cout<<current -> data<<"  ";
            current = current ->data;
        }
        std::cout << std::endl;
    }
};  
  
int main() {  
    LinkedList<int> myList;  
  
    myList.insert(1);  
    myList.insert(2);  
    myList.insert(3);  
    myList.insert(4);  
    myList.insert(5);  
  
    std::cout << "Original List: ";  
    myList.printList();  
  
    std::cout << "Size of the list: " << myList.getSize() << std::endl;  
  
    myList.remove(3);  
  
    std::cout << "List after removing 3: ";  
    myList.printList();  
  
    std::cout << "Does the list contain 4? " << (myList.search(4) ? "Yes" : "No") << std::endl;  
  
    return 0;  
}